package com.tingyuge.base.arithmetic.sort;

/**
 * Created by xiaodao
 * date: 2020/4/3
 * 快速排序
 */
public class QuickSort<T extends Comparable <T>> extends Sort<T> {
    @Override
    protected void sort() {
        sort(0,array.length);
    }

    /**
     * 对 [begin,end) 范围进行快速排序
     * 最好的nlog(n)
     * 最坏的O(n²)
     * 空间负载度: Olog(n)
     *
     * @param begin
     * @param end
     */
    private void sort(int begin, int end) { // T(n) =2* T(n/2) +O(n)
        if (end - begin < 2) {
            return;
        }

        //确定轴点位置 0(n) 的复杂度
        int mid = pivotIndex(begin, end);

        //对子序列也进行快排
        sort(begin, mid);//T(n/2)

        sort(mid + 1, end);//T(n/2)
    }

    /**
     * 找到轴点元素
     *
     * @param begin
     * @param end
     * @return 轴点元素的最终位置
     */
    private int pivotIndex(int begin, int end) {
        //随机选择一个元素进行一个交换
//       begin + Math.random()*(end-begin) //(begin,end]
        swap(begin,begin + (int)( Math.random()*(end-begin)));
        //备份begin位置的元素
        T pivot = array[begin];
        //end 指向最后一个元素
        end--;
       while (begin <end) {
           while (begin < end) {
               //1.先和最后的元素做一个比较.如果发生,轴点元素>=end 那么进行交换 end 覆盖轴点元素. begin++.,

               //如果轴点元素<end 那么 end --
               if (cmpElement(pivot,array[end])< 0) {
                   end--;
               } else {
                   //
                   //右边<=轴点  1 3 4 2 2小于1
                   array[begin++] = array[end];
                   break;
               }
           }
           //2.然后从头开始比较,如果轴点元素 > begin 那么就移动指针 begin++ 如果小于 那么 如  1 4 6 3 2 1 如6 <3 那么  1 3 3 1 6 将大于轴点的放到最后一个位置,
           while (begin < end) {
               //左边元素<pivot
               if (pivot.compareTo(array[begin]) > 0) {
                   begin++;
               } else {
                   array[end--] = array[begin];
                   break;
               }
           }
       }
       //元素放入最终的位置,找到需要交换的位置

        array[begin] = pivot;

       //返回轴点元素->begin==end 这个就是轴点元素
       return begin;



    }

    @Override
    public int compareTo(Sort<T> o) {
        return 0;
    }
}
